dataType arrayName[arraySize];

An array is distinguished from a normal variable 
by brackets [ and ].

• Arrays allow random access of elements. This makes accessing elements by their position faster.
• Arrays have better cache locality that can make a pretty big difference in performance.

// A character array in C/C++/Java

char arr1[] = {'g', 'e', 'e', 'k', 's'};



// An Integer array in C/C++/Java

int arr2[] = {10, 20, 30, 40, 50};



// Item at i'th index in array is typically accessed

// as "arr[i]".  For example arr1[0] gives us 'g'

// and arr2[3] gives us 40.

Searching in an Array

for(i = 0; i < N; i++)
{
    if(arr[i] == key)
    { 
        print "Element Found";
    }
    else
    {
        print "Element not Found";
    }
}

Insertion in Arrays

1. Insert elements at the end of the array.
2. Insert element at any given index in the array.

• Insert an element K at end in arr[]: The first step is to check if there is any space left in the array for new element. To do this check,
  

  if(len < N)
       // space left
  else
       // array is full
  

  If there is space left for the new element, insert it directly at the end at position len + 1 and index len:
  

  arr[len] = k;
  

  
  Time Complexity of this insert operation is constant, i.e. O(1) as we are directly inserting the element in a single operation.
  
• Insert an element K at position, pos in arr[]: The first step is to check if there is any space left in the array for new element. To do this check,
  

  if(len < N)
       // space left
  else
       // array is full
  

  Now, if there is space left, the element can be inserted. The index of the new element will be idx = pos - 1.
  
  Now, before inserting the element at the index idx, shift all elements from the index idx till end of the array to the right by 1 place. This can be done as:
  

  for(i = len-1; i >= idx; i--)
  {
      arr[i+1] = arr[i];
  }
  

  After shifting the elements, place the element K at index idx.
  

  arr[idx] = K;
  

  
  Time Complexity in worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the right.
  

Deletion in Arrays

for(i = 0; i < N; i++)
{
    if(arr[i] == K)
        idx = i; return;
    else
        Element not Found;
}

for(i = idx+1; i < len; i++)
{
    arr[i-1] = arr[i];
}

len = len-1;

• Shift all elements after K-th element to the left by K positions.
• Fill the K blank spaces at the end of the array by first K elements from the original array.

Implementations

• Simple Method: The simplest way to rotate an array is to implement the above visually observed approach by using extra space.
  
  1. Store the first K elements in a temporary array say temp[].
  2. Shift all elements after K-th element to the left by K positions in the original array.
  3. Fill the K blank spaces at the end of the original array by the K elements from the temp array.

  Say, arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2
  1) Store first K elements in a temp array
     temp[] = [1, 2]
  2) Shift rest of the arr[]
     arr[] = [3, 4, 5, 6, 7, 6, 7]
  3) Store back the K elements from temp
     arr[] = [3, 4, 5, 6, 7, 1, 2]
  

  
  Time Complexity: O(N), where N is the number of elements in the array.
  Auxiliary Space: O(K) where K is the number of places by which elements will be rotated.
  


• Another Method (Without extra space): We can also rotate an array by avoiding the use of temporary array. The idea is to rotate the array one by one K times.
  

  leftRotate(arr[], d, n)
  start
    For i = 0 to i < d
      Left rotate all elements of arr[] by one
  end
  

  
  To rotate an array by 1 position to the left:
  
  1. Store the first element in a temporary variable say temp.
  2. Left shift all elements after the first element by 1 position. That is, move arr[1] to arr[0], arr[2] to arr[1] and so on.
  3. Initialize arr[N-1] with temp.
  
  To rotate an array by K position to the left, repeat the above process K times.
  Take the same example,
  

  arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2
  
  Rotate arr[] one by one 2 times.
  
  After 1st rotation: [2, 3, 4, 5, 6, 7, 1]
  After 2nd rotation: [ 3, 4, 5, 6, 7, 1, 2]
  

  Time Complexity: O(N*K), where N is the number of elements in the array and K is the number of places by which elements will be rotated.
  Auxiliary Space: O(1).
  


• Juggling Algorithm: This is an extension of the above method. Instead of moving one by one, divide the array in different sets, where number of sets is equal to GCD of N and K and move the elements within sets.
  
  If GCD is 1 as is for the above example array (N = 7 and K = 2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
  
  Here is an example for N = 12 and K = 3. GCD of N and K is 3:
  

  Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
  
  a) Elements are first moved in first set – (See below 
     diagram for this movement)
  
  
  
         arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}
  
  b) Then in second set.
         arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}
  
  c) Finally in third set.
         arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}
  

  Time Complexity: O(N), where N is the number of elements in the array.
  Auxiliary Space: O(1).
  

Input  : arr[] = {1, 2, 3}
Output : arr[] = {3, 2, 1}

Input :  arr[] = {4, 5, 1, 2}
Output : arr[] = {2, 1, 5, 4}

Iterative Solution

• Method 1 (Using Temporary Array): The idea is to first copy all of the elements of the given array in a temporary array. Then traverse the temporary array from end and replace elements in original array by elements of temp array.
  
  This method will take extra space in order of O(N).
  
• Method 2 (Efficient): This method is efficient then the above method and avoids using extra spaces. The idea is to traverse the array from both ends and keep swapping elements from both ends until middle of the array is reached.
  

  1) Initialize start and end indexes as 
     start = 0, end = N-1
  2) In a loop, swap arr[start] with arr[end] 
     and change start and end as follows :
         start = start + 1, 
         end = end – 1
  

  For Example:
  
  Time Complexity: O(N), where N is the number of elements in the array.
  

Recursive Solution

1) Initialize start and end indexes as 
   start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Given an array of integers of size 'n'.
Our aim is to calculate the maximum sum of 'k' 
consecutive elements in the array.

Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
         k = 4 
Output : 39
We get maximum sum by adding subarray {4, 2, 10, 23}
of size 4.

Input  : arr[] = {2, 3}
         k = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.

Window Sliding Technique

1. We compute the sum of first k elements out of n terms using a linear loop and store the sum in variable window_sum.
2. Then we will graze linearly over the array till it reaches the end and simultaneously keep track of maximum sum.
3. To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block .

• Vector
• List

Vector

• We do not need to pass size as an extra parameter when we pass vector.
• Vectors have many in-built functions for erasing an element, inserting an element etc.
• Vectors support dynamic sizes, we do not have to initially specify the size of a vector. We can also resize a vector.
• There are many other functionalities vector provide.

#include< vector >

vector< Type_of_element > vector_name;

Here, Type_of_element can be any valid C++ data type,
or can be any other container also like Pair, List etc.

• begin() – Returns an iterator pointing to the first element in the vector.
• end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector.
• size() – Returns the number of elements in the vector.
• capacity() – Returns the size of the storage space currently allocated to the vector expressed as number of elements.
• empty() – Returns whether the container is empty.
• push_back() – It push the elements into a vector from the back.
• pop_back() – It is used to pop or remove elements from a vector from the back.
• insert() – It inserts new elements before the element at the specified position.
• erase() – It is used to remove elements from a container from the specified position or range.
• swap() – It is used to swap the contents of one vector with another vector of same type and size.
• clear() – It is used to remove all the elements of the vector container.
• emplace() – It extends the container by inserting new element at position.
• emplace_back() – It is used to insert a new element into the vector container, the new element is added to the end of the vector.

Size : 5
Vector is not empty
Output of begin and end: 1 2 3 4 5 
The first element is: 5
The last element is: 20
Vector size after erase(): 0

List

#include< list >

list< Type_of_element > list_name;

Here, Type_of_element can be any valid C++ data type,
or can be any other container also like Pair, List etc.

• front() – Returns the value of the first element in the list.
• back() – Returns the value of the last element in the list.
• push_front(g) – Adds a new element ‘g’ at the beginning of the list.
• push_back(g) – Adds a new element ‘g’ at the end of the list.
• pop_front() – Removes the first element of the list, and reduces the size of the list by 1.
• pop_back() – Removes the last element of the list, and reduces the size of the list by 1.
• begin() and end() – begin() function returns an iterator pointing to the first element of the list.
• empty() – Returns whether the list is empty(1) or not(0).
• insert() – Inserts new elements in the list before the element at a specified position.
• reverse() – Reverses the list.
• size() – Returns the number of elements in the list.
• sort() – Sorts the list in increasing order.

List 1 (gqlist1) is :     0    2    4    6    
8    10    12    14    16    18

List 2 (gqlist2) is :     27    24    21    18    
15    12    9    6    3    0

gqlist1.front() : 0
gqlist1.back() : 18
gqlist1.pop_front() :     2    4    6    8    
10    12    14    16    18

gqlist2.pop_back() :     27    24    21    18    
15    12    9    6    3

gqlist1.reverse() :     18    16    14    12    
10    8    6    4    2

gqlist2.sort():     3    6    9    12    
15    18    21    24    27

• begin() :- This function is used to return the beginning position of the container.
• end() :- This function is used to return the after end position of the container.
  
  
  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  // C++ code to demonstrate the working of

  // iterator, begin() and end()

  #include<iostream>

  #include<iterator> // for iterators

  #include<vector> // for vectors

  using namespace std;

  int main()

  {

  vector<int> ar = { 1, 2, 3, 4, 5 };

  // Declaring iterator to a vector

  vector<int>::iterator ptr;

  // Displaying vector elements using begin() and end()

  cout << "The vector elements are : ";

  for (ptr = ar.begin(); ptr < ar.end(); ptr++)

  cout << *ptr << " ";

  return 0;

  }

  הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  Run
  Output:

  The vector elements are : 1 2 3 4 5 
  

• advance() :- This function is used to increment the iterator position till the specified number mentioned in its arguments.
  
  
  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  26

  27

  28

  29

  // C++ code to demonstrate the working of

  // advance()

  #include<iostream>

  #include<iterator> // for iterators

  #include<vector> // for vectors

  using namespace std;

  int main()

  {

  vector<int> ar = { 1, 2, 3, 4, 5 };

  // Declaring iterator to a vector

  vector<int>::iterator ptr = ar.begin();

  // Using advance() to increment iterator position

  // points to 4

  advance(ptr, 3);

  // Displaying iterator position

  cout << "The position of iterator after advancing is : ";

  cout << *ptr << " ";

  return 0;

  }

  הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  Run
  Output:

  The position of iterator after advancing is : 4 
  

• next() :- This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.
  
• prev() :- This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.
  
  
  // C++ code to demonstrate the working of

  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  26

  27

  28

  29

  30

  // C++ code to demonstrate the working of

  // next() and prev()

  #include<iostream>

  #include<iterator> // for iterators

  #include<vector> // for vectors

  using namespace std;

  int main()

  {

  vector<int> ar = { 1, 2, 3, 4, 5 };

  // Declaring iterators to a vector

  vector<int>::iterator ptr = ar.begin();

  vector<int>::iterator ftr = ar.end();

  // Using next() to return new iterator points to 4

  auto it = next(ptr, 3);

  // Using prev() to return new iterator points to 3

  auto it1 = prev(ftr, 3);

  // Displaying iterator position

  cout << "The position of new iterator using next() is : ";

  cout << *it << " "; cout << endl;

  // Displaying iterator position

  cout << "The position of new iterator using prev() is : ";

  cout << *it1 << " ";

  cout << endl;

  return 0;

  }

  הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  Run
  Output:

  The position of new iterator using next() is : 4 
  The position of new iterator using prev()  is : 3 
  

• inserter() :- This function is used to insert the elements at any position in the container. It accepts 2 arguments, the container and iterator to position where the elements have to be inserted.
  
  
  int main()

  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  26

  27

  28

  29

  // C++ code to demonstrate the working of inserter()

  #include<iostream>

  #include<iterator> // for iterators

  #include<vector> // for vectors

  using namespace std;

  int main()

  {

  vector<int> ar = { 1, 2, 3, 4, 5 };

  vector<int> ar1 = {10, 20, 30};

  // Declaring iterator to a vector

  vector<int>::iterator ptr = ar.begin();

  // Using advance to set position

  advance(ptr, 3);

  // copying 1 vector elements in other using inserter()

  // inserts ar1 after 3rd position in ar

  copy(ar1.begin(), ar1.end(), inserter(ar,ptr));

  // Displaying new vector elements

  cout << "The new vector after inserting elements is : ";

  for (int &x : ar)

  cout << x << " ";

  return 0;

  }

  הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  Run
  Output:

  The new vector after inserting elements is : 1 2 3 10 20 30 4 5 
  

type array-name[];

OR

type[] array-name;

// both are valid declarations
int intArray[]; 
or int[] intArray; 

byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];

array-name = new type [size];

• type specifies the type of data being allocated.
• size specifies the number of elements in the array.
• array-name is the name of array variable that is linked to the array.

int intArray[];    //declaring array
intArray = new int[20];  // allocating memory to array

int[] intArray = new int[20]; // combining both statements in one

 

// Accessing the elements of the specified array

for (int i = 0; i < arr.length; i++)

  System.out.println("Element at index " + i + 

                                " : "+ arr[i]);



Here, arr.length gives the number of elements 

present in the array named arr.

Element at index 0 : 10
Element at index 1 : 20
Element at index 2 : 30
Element at index 3 : 40
Element at index 4 : 50

ArrayList in Java

• ArrayList(): This constructor is used to build an empty array list.
• ArrayList(Collection c): This constructor is used to build an array list initialized with the elements from collection c.
• ArrayList(int capacity): This constructor is used to build an array list with the specified initial capacity.

ArrayList arrli = new ArrayList();

[1, 2, 3, 4, 5]
[1, 2, 3, 5]
1 2 3 5 

Vector Class in Java

• Vector implements a dynamic array that means it can grow or shrink as required. Like an array, it contains components that can be accessed using an integer index.
• They are very similar to ArrayList but Vector is synchronized and has some legacy method, which the collection framework does not contain.
• It extends AbstractList and implements List interfaces.

• Vector(): Creates a default vector of initial capacity 10.
• Vector(int size): Creates a vector whose initial capacity is specified by size.
• Vector(int size, int incr): Creates a vector whose initial capacity is specified by size and the increment is specified by incr. It specifies the number of elements to allocate each time a vector is resized upwards.
• Vector(Collection c): Creates a vector that contains the elements of collection c.

Vector is [1, 2, 3, 4, 3]

Problem #1 : Range Sum Queries using Prefix Sum

Input 
[4, 5, 3, 2, 5]
3
0 3
2 4
1 3
Output
14 (4+5+3+2)
10 (3+2+5)
10 (5+3+2)

prefix[] = Array stores the sum (A[0]+A[1]+....A[i]) at index i.
if l == 0 :
    sum(l,r) = prefix[r]
else :
    sum(l,r) = prefix[r] - prefix[l-1]

// n : size of array
// q : Number of queries
// l, r : Finding Sum of range between index l and r 
// l and r (inclusive) and 0 based indexing
void range_sum(arr, n)
{
    prefix[n] = {0}
    prefix[0] = arr[0]
    for i = 1 to n-1 :
        prefix[i] = a[i] + prefix[i-1]

    for (i = 1 to q )
    {
        if (l == 0) 
        {
            ans = prefix[r]
            print(ans)
        }
        else 
        {
            ans = prefix[r] - prefix[l-1]
            print(ans)
        }
    }
}

Problem #2 : Equilibrium index of an array

A[0] + A[1] + ... A[i-1] = A[i+1] + A[i+2] ... A[n-1]

Input
[-7, 1, 5, 2, -4, 3, 0]
Output
3
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

for (i=0 to n-1)
{
    leftsum = 0
    for (j = 0 to i-1)
        leftsum += arr[i]
    rightsum = 0
    for (j = i+1 to n-1)
        rightsum += arr[i]

    if leftsum == rightsum :
        return i
}

// n : size of array
int eqindex(arr, n)
{
    sum = 0
    leftsum = 0
    for (i=0 to n-1)
        sum += arr[i]

    for (i=0 to n-1)
    {
        // now sum will be righsum for index i
        sum -= a[i]
        if (sum == leftsum )
            return i
        leftsum += a[i]
    }
}

Problem #3 : Largest Sum Subarray

Input
[-3, 4, -1, -2, 1, 5]
Output
7
(4+(-1)+(-2)+1+5)

//n : size of array
int largestsum(arr, n)
{
    max_so_far = INT_MIN
    max_ending_here = 0

    for (i=0 to n-1)
    {
        max_ending_here += arr[i]
        if max_so_far < max_ending_here :
            max_so_far = max_ending_here

        if max_ending_here < 0 :
            max_ending_here = 0
    }

    return max_so_far
}

Problem #4 : Merge two sorted Arrays

Input
1 3 4 6
2 5 7 8
Output
1 2 3 4 5 6 7 8

// input arrays - arr1(size m), arr2(size n)
void merge_sorted(arr1, arr2, m, n)
{
    arr3[m+n] // merged array
    i=0,j=0,k=0
    while(i < m && j < n) 
    {
        if arr1[i] < arr2[j] :
            arr3[k++] = arr1[i++]
        else :
            arr3[k++] = arr2[j++]
    }
    while(i < m)
        arr3[k++] = arr1[i++]
    while(j < n)
        arr3[k++] = arr2[j++]
}